# 队列Queue 定义
# 新加入的数据项必须在数据集末尾等待，而等待时间最长的数据项则是队首
# 先进先出， 先到先服务
# 只有一个入口和一个出口， 且中间不能插入，不能取出

# 栗子： 计算机进程调度， 进程数远多于CPU的核心数， 有的进程还要等待不同类型的I/O事件
# 调度原则综合了 “先到先服务”及“资源充分利用”两个出发点
# Queue 是一个有次序的数据集，

class Queue:
    def __init__(self):
        self.items = []  # 定义类属性为 空列表数据类型
    
    def isEmpty(self):
        return self.items == []  # bool判断列表是否为空
    
    def enqueue(self, item):
        # 算法复杂度为O(n)
        self.items.insert(0, item)  # 在列表首位插入元素
    
    def dequeue(self):
        # 算法复杂度为O(1)
        return self.items.pop()  # 列表移除元素
    
    def size(self):
        return len(self.items)  # 计算列表元素个数

# 热土豆问题，（约瑟夫问题） 击鼓传花，
# 参加游戏的人名列表，传土豆的次数num
from pythonds.basic.queue import Queue

def hoPotota(namlst, num):
    simqueue = Queue()
    for name in namlst:
        simqueue.enqueue(name)
    
    while simqueue.size() > 1:
        for i in range(num):
            simqueue.dequeue()
    
    return simqueue.dequeue()


if __name__ == '__main__':
    q1 = Queue()
    q1.enqueue(1)
    q1.enqueue('body')
    q1.enqueue('girl')
    q1.enqueue('goddess')
    print(q1.isEmpty(),'\n', q1.size(),'\n',q1.items)
    
    namlist = ['Bill', 'David', 'Susan', 'Jane', 'Kent', 'Brad']
    num = 7
    print(hoPotota(namlist, num))